package datastructure.bst;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author XY
 * @version 1.0
 * @date 2021/9/28 15:24
 * @Description 二分搜索树
 */
public class BST<E extends Comparable<E>> {

    private class Node{
        public E e;
        public Node left;
        public Node right;

        public Node(E e){
            this.e =e;
            left = null;
            right=null;
        }
    }

    private Node root;
    private int size;

    public BST(){
        root = null;
        size = 0;

    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public void add(E e){
//        if(root == null){
//            root = new Node(e);
//            size ++;
//        }else{
//            add(root ,e);
//        }
        root = add2(root,e);
    }

    private void add(Node node,E e){
        //如果当前元素与需要添加的元素相等，就直接返回
        if(e.compareTo(node.e)==0){
            return;
        }
        if(e.compareTo(node.e)<0&&node.left==null){
            node.left=new Node(e);
            size++;
            return ;
        }
        if(e.compareTo(node.e)>0&&node.right==null){
            node.right=new Node(e);
            size++;
            return ;
        }
        //递归左子树
        if(e.compareTo(node.e)<0){
            add(node.left,e);
        }else{
            //递归右子树
            add(node.right,e);
        }
    }

    //优化
    private Node add2(Node node,E e){
        //如果递归到某个节点为null， 那么插入的地方一定是这个节点。
        if(node==null){
            size++;
            return new Node(e);
        }
        if(e.compareTo(node.e)<0){
            node.left = add2(node.left,e);
        }else if (e.compareTo(node.e)>0){
            node.right = add2(node.right,e);
        }
        return node;
    }

    //树中是否包含某个元素
    public boolean contains(E e){
        return contains(root,e);
    }

    private boolean contains(Node node, E e){
        if(node==null){
            return false;
        }
        if(e.compareTo(node.e)==0){
            return true;
        }else if(e.compareTo(node.e)<0){
            contains(node.left,e);
        }else{
            contains(node.right,e);
        }
        return false;
    }

    //前序遍历,根左右
    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node node){
        if(node==null){
            return ;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

    //前序遍历非递归写法
    public void preOrderNR(){
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);
            if(cur.right!=null){
                stack.push(cur.right);
            }
            if(cur.left!=null){
                stack.push(cur.left);
            }
        }
    }

    //中序遍历,左根右
    public void midOrder(){
        midOrder(root);
    }

    private void midOrder(Node node){
        if(node==null){
            return ;
        }
        midOrder(node.left);
        System.out.println(node.e);
        midOrder(node.right);
    }

    //后序遍历,左右根
    public void postOrder(){
        postOrder(root);
    }

    private void postOrder(Node node){
        if(node==null){
            return ;
        }
        midOrder(node.left);
        midOrder(node.right);
        System.out.println(node.e);
    }

    //层序遍历（广度优先遍历）
    public void levelOrder(){
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            Node remove = queue.remove();
            System.out.println(remove.e);
            if(remove.left!=null){
                queue.add(remove.left);
            }
            if(remove.right!=null){
                queue.add(remove.right);
            }
        }
    }

    //寻找二分搜索树的最小元素
    public E minimum(){
        if(size == 0 ){
            throw  new RuntimeException("BST is empty");
        }
        return minimum(root).e;
    }

    private Node minimum(Node e){
        if(e.left == null){
            return e;
        }
        return minimum(e.left);
    }

    //寻找二分搜索树的最大元素
    public E maximum(){
        if(size == 0 ){
            throw  new RuntimeException("BST is empty");
        }
        return maximum(root).e;
    }

    private Node maximum(Node e){
        if(e.right == null){
            return e;
        }
        return maximum(e.right);
    }

    //删除最小元素
    public E removeMin(){
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    private Node removeMin(Node node){

        //判断是最小的节点了
        if(node.left == null){
            //这里如果右子节点为null也不影响
            Node rightNode = node.right;
//            可省略？？
            node.right=null;
            size --;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    //删除最大元素
    public E removeMax(){
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node){

        //判断是最大的节点了
        if(node.right == null){
            //这里如果左子节点为null也不影响
            Node leftNode = node.left;
            node.left=null;
            size --;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    public void remove(E e){
        root = remove(root,e);
    }

    private Node remove(Node node, E e) {
        if(node==null){
            return null;
        }
        if(e.compareTo(node.e)<0){
            node.left = remove(node.left,e);
            return node;
        }else if(e.compareTo(node.e)>0){
            node.right = remove(node.right,e);
            return node;
        }else{
            if(node.left==null){
                //这里如果右子节点为null也不影响
                Node rightNode = node.right;
                //可省略？？
                node.right=null;
                size --;
                return rightNode;
            }
            if(node.right==null){
                //这里如果左子节点为null也不影响
                Node leftNode = node.left;
                node.left=null;
                size --;
                return leftNode;
            }
            //要删除的节点左右孩子都存在，选在该节点右子树中最小的元素成为删除后的新的根节点
            Node minimum = minimum(node.right);
            minimum.right = removeMin(node.right);
            minimum.left = node.left;
            node.left = node.right = null;
            return minimum;

        }
    }

}
